class Solution {
public:
    struct cmp1{
        bool operator()(const int& a,const int& b){
            return a > b;
        }
    }; 
    struct cmp2{
        bool operator()(const int& a,const int& b){
            return a < b;
        }
    };          
                                        
    priority_queue<int,vector<int>,cmp1> que1;
    priority_queue<int,vector<int>,cmp2> que2;   
    unordered_map<int,int> hash;                                    
                                        
    double getMid(int k){
        if(k % 2 != 0) return que1.top() * 1.0;
        return 0.5 * que1.top() + que2.top() * 0.5;
    }                            
                                        
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        for(int i = 0;i < k;i++) que1.push(nums[i]);
        for(int i = 0;i < k/2;i++){
            que2.push(que1.top());
            que1.pop();
        }
        
        
        vector<double> ans;
        int l = 0,r = k;
        while(r < n){
            int balance = 0;
            ans.push_back(getMid(k));
            
            hash[nums[l]]++;
            if(nums[l] >= que1.top()){
                balance--;
            }else{
                balance++;
            }
            l++;
            
            if(nums[r] >= que1.top()){
                que1.push(nums[r]);
                balance++;
            }else{
                que2.push(nums[r]);
                balance--;
            }
            r++;
            
            
            if(balance > 0){
                que2.push(que1.top());
                que1.pop();
            }else if(balance < 0){
                que1.push(que2.top());
                que2.pop();
            }
            
            while(!que1.empty() && hash[que1.top()] > 0){
                hash[que1.top()]--;
                que1.pop();
            }
            while(!que2.empty() && hash[que2.top()] > 0){
                hash[que2.top()]--;
                que2.pop();
            }
        }
        
        ans.push_back(getMid(k));
        
        return ans;
        
    }
};
